package com.huangyi;

import java.util.Random;

public class Main {
    public static void main(String[] args) {
        //颜色分类
        class Solution {
            private void swap(int[] a, int i, int j) {
                int t = a[i]; a[i] = a[j]; a[j] = t;
            }

            public void sortColors(int[] nums) {
                int left = -1, right = nums.length, i = 0;
                while (i < right) {
                    if (nums[i] == 0)       swap(nums, ++left, i++); // 左区扩张
                    else if (nums[i] == 1)  i++;                     // 中区自然累积
                    else                    swap(nums, --right, i);  // 右区收缩，i不动
                }
            }
        }

        //排序数组
        class Solution2 {
            private void swap(int[] a, int i, int j) {
                int t = a[i]; a[i] = a[j]; a[j] = t;
            }

            public int[] sortArray(int[] nums) {
                qsort(nums, 0, nums.length - 1);
                return nums;
            }

            private void qsort(int[] nums, int l, int r) {
                if (l >= r) return; // 递归基

                // 随机基准，降低退化概率
                int key = nums[new Random().nextInt(r-l+1) + l];

                int left = l - 1, i = l, right = r + 1;
                // 不变式：
                // [l, left]     < key
                // [left+1, i-1] = key
                // [i, right-1]   未处理
                // [right, r]     > key
                while (i < right) {
                    if (nums[i] < key ) {
                        swap(nums, ++left, i++);
                    } else if (nums[i] > key ) {
                        swap(nums, --right, i);   // i 不动：换来的还未检查
                    } else {
                        i++;
                    }
                }

                // 递归两端；等于 key 的中段 [left+1, right-1] 已就位
                qsort(nums, l, left);
                qsort(nums, right, r);
            }
        }
    }
}